package com.wuyou.mid;

import java.util.Collections;

/**
 * 最大二叉树
 */
public class ConstructMaximumBinaryTree {

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 6, 0, 5};
        solution_1(nums);
    }

    public static TreeNode solution_1(int[] nums) {
        int maxNum = 0;
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxNum) {
                maxNum = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode();
        root.val = maxNum;
        int[] left = new int[maxIndex];
        int[] right = new int[nums.length - maxIndex - 1];
        System.arraycopy(nums, 0, left, 0, left.length);
        if (maxIndex < nums.length - 1) {
            System.arraycopy(nums, maxIndex + 1, right, 0, right.length);
        }

         constructLeftTree(root, left);
         constructRightTree(root, right);
        return root;
    }

    public static void constructLeftTree(TreeNode root, int[] left) {

        if (left.length <= 0) {
            return;
        }
        int maxNum = 0;
        int maxIndex = 0;
        for (int i = 0; i < left.length; i++) {
            if (left[i] > maxNum) {
                maxNum = left[i];
                maxIndex = i;
            }
        }
        TreeNode leftNode = new TreeNode();
        leftNode.val = maxNum;
        root.left = leftNode;
        if (left.length == 1) {
            return;
        }
        int[] leftSub = new int[maxIndex];
        int[] rightSub = new int[left.length - maxIndex - 1];
        System.arraycopy(left, 0, leftSub, 0, leftSub.length);
        if (maxIndex < left.length - 1) {
            System.arraycopy(left, maxIndex + 1, rightSub, 0, rightSub.length);
        }
         constructLeftTree(leftNode, leftSub);
         constructRightTree(leftNode, rightSub);

    }

    public static void constructRightTree(TreeNode root, int[] right) {
        if (right.length <= 0) {
            return;
        }
        int maxNum = 0;
        int maxIndex = 0;
        for (int i = 0; i < right.length; i++) {
            if (right[i] > maxNum) {
                maxNum = right[i];
                maxIndex = i;
            }
        }

        TreeNode rightNode = new TreeNode();
        rightNode.val = maxNum;
        root.right = rightNode;
        if (right.length == 1) {
            return;
        }
        int[] leftSub = new int[maxIndex];
        int[] rightSub = new int[right.length - maxIndex - 1];
        System.arraycopy(right, 0, leftSub, 0, leftSub.length);
        if (maxIndex < right.length - 1) {
            System.arraycopy(right, maxIndex + 1, rightSub, 0, rightSub.length);
        }

        constructLeftTree(rightNode, leftSub);
        constructRightTree(rightNode, rightSub);
    }

}
